#include "graph_support/TestDejkstra.h"

#include <vector>

#include "graph_support/utils/CollectionsInit.h"
#include "graph_support/utils/test_my_graph/BoostTestUtils.h"
#include "graph_support/impls/vector/VectorGraph.h"
#include "graph_support/alg/shortest_path/Dejkstra.h"

using namespace GRAPH_SUPPORT_NS::impls::vector;
using namespace GRAPH_SUPPORT_NS::alg::shortest_path;
using namespace GRAPH_SUPPORT_NS::utils;

namespace
{

void fillVector( std::vector< int > & vec )
{
	for ( int i = 0; i < vec.size(); i++ )
	{
		vec[i] = i;
	}
}

}

void TestEdgesConnection()
{
	typedef VectorGraphTmpl< int > GraphI;
	typedef GraphI::GrVertex GrVertex;
	typedef GraphI::VertexIterator VertexIterator;
	typedef GraphI::EdgeIterator EdgeIterator;

	int n = 5;
	std::vector< GrVertex > vec( n );
	fillVector( vec );
	GraphI gr( vec );

	std::vector< GraphI::GrVertex > vertices;
	for ( VertexIterator it = gr.getVerticesBeg(); it != gr.getVerticesEnd(); ++it )
	{
		vertices.push_back( * it );
	}

	gr.addEdge( 1, 3 );

	std::vector< GraphI::GrEdgePtr > outEdges;
	for ( EdgeIterator it = gr.getEdgsBeg( 1 ); it != gr.getEdgsEnd( 1 ); ++it )
	{
		outEdges.push_back( * it );
	}

	BOOST_CHECK_EQUAL( 1, outEdges.size() );
	GrVertex beg = outEdges[0]->beg();
	GrVertex end = outEdges[0]->end();
	BOOST_CHECK_EQUAL( vertices[1], beg );
	BOOST_CHECK_EQUAL( vertices[3], end );
}

void TestDistanceSearch()
{
	typedef VectorGraphTmpl< int > GraphI;
	typedef GraphI::GrVertex GrVertex;
	typedef GraphI::VertexIterator VertexIterator;
	typedef GraphI::EdgeIterator EdgeIterator;

	int n = 5;
	std::vector< GrVertex > vec( n );
	fillVector( vec );
	GraphI gr( vec );

	BOOST_CHECKPOINT( "TestDistanceSearch was graph initialized" );

	std::vector< GrVertex > vertices;
	for ( VertexIterator it = gr.getVerticesBeg(); it != gr.getVerticesEnd(); ++it )
	{
		vertices.push_back( * it );
	}

	BOOST_CHECKPOINT( "TestDistanceSearch vertices were spied" );

	gr.addEdge( 0, 1 );
	gr.addEdge( 0, 2 );
	gr.addEdge( 1, 3 );
	gr.addEdge( 3, 4 );
	gr.addEdge( 2, 4 );

	BOOST_CHECKPOINT( "TestDistanceSearch some edges were added" );

	Dejkstra< GraphI > dejkstra( gr );
	dejkstra( 0 );

	BOOST_CHECKPOINT( "TestDistanceSearch Dejcstra-run completed" );

	BOOST_CHECK_EQUAL( 0, dejkstra.getDistance( 0 ) );
	BOOST_CHECK_EQUAL( 2, dejkstra.getDistance( 3 ) );
	BOOST_CHECK_EQUAL( 2, dejkstra.getDistance( 4 ) );
}

void TestCharVerticesDejkstra()
{
	typedef VectorGraphTmpl< const char * > GraphCh;
	typedef GraphCh::GrVertex GrVertex;

	std::vector< GrVertex > names =
			arr2vector< GrVertex >( ( GrVertex const [] )
				{ "a", "b", "c", "d", "e", "f", "g", "LAST" } );
	BOOST_CHECK_EQUAL( 8, names.size() );

	GraphCh gr( names );

	gr.addEdge( "a", "b" );
	gr.addEdge( "b", "c" );
	gr.addEdge( "c", "d" );
	gr.addEdge( "d", "e" );
	gr.addEdge( "e", "LAST" );

	{
	Dejkstra< GraphCh > dejkstra( gr );
	dejkstra( "a" );
	BOOST_CHECK_EQUAL( 5, dejkstra.getDistance( "LAST" ) );
	}

	gr.addEdge( "a", "d" );
	{
	Dejkstra< GraphCh > dejkstra( gr );
	dejkstra( "a" );
	BOOST_CHECK_EQUAL( 3, dejkstra.getDistance( "LAST" ) );
	}
}
